class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        trie = {}
        for word in words:
            if not word: continue
            cur = trie
            for w in word:
                cur = cur.setdefault(w, {})
            cur["#"] = "#"  # 结束标志
        res = []
		#亮点主要在这里 字典树是使用字典dict进行构建的
		#平常自己实现树 都是自己定义树的节点结构 python灵活的数据结构可以多样的构建树

        def dfs(word, idx, cnt, cur):
            if idx == len(word):
                # 组成个数 > 2, 并且以#结束的
                if cnt >= 1 and "#" in cur:
                    return True
                return False
            if "#" in cur:
                if dfs(word, idx, cnt + 1, trie):
                    return True
            if word[idx] not in cur:
                return False
            if dfs(word, idx + 1, cnt, cur[word[idx]]):
                return True
            return False

        for word in words:
            # 参数分别为, 单词word, 位置idx, 目前为止有几个单词组成了cnt, 字典树trie
            if dfs(word, 0, 0, trie):
                res.append(word)
        return res

#作者：powcai
#链接：https://leetcode-cn.com/problems/concatenated-words/solution/trie-ha-xi-by-powcai/
#来源：力扣（LeetCode）
#著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。




#通过定义节点可以很优雅的实现Trie前缀树
# 题解可以和字典树的构建写在一起!!!
class TrieNode:
    
    def __init__(self, char=None, next=[], isEnd=False):
        self.char = char
        self.next = { n.char:n for n in next }
        self.isEnd = isEnd

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tmp = self.root
        for char in word:
            if char not in tmp.next:
                tmp.next[char] = TrieNode(char)
            tmp = tmp.next[char]
        tmp.isEnd = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tmp = self.root
        for char in word:
            if char not in tmp.next:
                return False
            tmp = tmp.next[char]
        
        return True if tmp.isEnd else False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tmp = self.root
        for char in prefix:
            if char not in tmp.next:
                return False
            tmp = tmp.next[char]
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)